package CatchRainwater;

public class Solution {
    /*解题思路：
1. 该问题可以使用双指针法来解决，双指针分别指向数组的起始和末尾，
以模拟从两侧向中间移动的过程。
2. 初始化左指针left为0，右指针right为数组最后一个元素的索引，
以及两个变量maxLeft和maxRight，它们分别用来跟踪左侧和右侧的最大高度。
初始化总雨水量totalWater为0。
3. 进入一个循环，循环条件是左指针小于右指针，这意味着我们会一直移动指针直到它们相遇。
4. 在每次迭代中，首先比较height[left]和height[right]，
以确定哪个指针所指的位置可以存储雨水。我们选择当前高度较小的柱子进行处理，
因为它决定了当前位置能存储的雨水量。
5. 如果height[left] <= height[right]，说明左侧柱子较低，
我们需要处理左侧。首先，检查当前左侧柱子的高度是否大于或等于maxLeft，
如果是，则更新maxLeft为当前左侧柱子的高度。否则，说明当前位置可以存储雨水，
将(maxLeft - height[left])累加到总雨水量totalWater，并将left指针向右移动一位。
6. 如果height[left] > height[right]，则右侧柱子较低，
我们需要处理右侧。类似地，首先检查当前右侧柱子的高度是否大于或等于maxRight，
如果是，则更新maxRight为当前右侧柱子的高度。否则，
累加(maxRight - height[right])到总雨水量totalWater，并将right指针向左移动一位。
7. 重复步骤4到步骤6，直到左指针和右指针相遇。
8. 返回总雨水量totalWater作为最终答案。
注释已经在代码中添加，帮助解释每一步的操作。
这个算法的关键在于维护最大高度和根据当前柱子高度来计算存储雨水量。*/
    public static int trap(int[] height) {
    int left = 0; // 左指针
    int right = height.length - 1; // 右指针
    int maxLeft = 0; // 左侧最大高度
    int maxRight = 0; // 右侧最大高度
    int totalWater = 0; // 总雨水量

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= maxLeft) {
                maxLeft = height[left];
            } else {
                totalWater += maxLeft - height[left];
            }
            left++;
        } else {
            if (height[right] >= maxRight) {
                maxRight = height[right];
            } else {
                totalWater += maxRight - height[right];
            }
            right--;
        }
    }

    return totalWater;
}

}